package me.zk.practice1.hw;

import java.util.*;

/**
 * @author zhangkai
 * @date 2023/8/11 10:44
 */
public class HWBJJ37 {
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());

        int[] nums = new int[n];
        int sum = 0;
        int max = 0;
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
            sum += nums[i];
            max = Math.max(max,nums[i]);
        }
        int half = max/2;
        if (sum%2!=0 || max>half) {
            System.out.println(-1);
            return;
        }

    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入有几块雨花石
        int n = Integer.parseInt(sc.nextLine());
        // 输入每块雨花石的重量
        int[] nums = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 获取雨花石的总重量
        int sum = Arrays.stream(nums).sum();
        // 因为要两个人平分，不能平分的话，直接返回-1
        if (sum % 2 != 0) {
            System.out.println(-1);
            return;
        }
        // 雨花石的一半重量，也就是两个人得到的重量，计算目标
        int avg = sum / 2;
        // 采用动态规划算法
        int[][] dp = new int[n + 1][avg + 1];
        for (int i = 0; i <= avg; i++) {
            dp[0][i] = n;
        }
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];

            for (int j = 1; j <= avg; j++) {
                if (j < num) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - num] + 1);
                }
            }
        }
        if (dp[n][avg] == n) {
            System.out.println(-1);
        } else {
        // 输出最优解
            System.out.println(dp[n][avg]);
        }
    }
}
